1. Field of the Invention
This invention relates to a new concept for structuring an information processing system. In terms of terminology which has become well founded in the art (in reference, for example, the text book by C. G. Bell and A. Newell, "Computer Structures: Readings and Examples" published in 1971 by McGraw-Hill, Inc., New York, New York, and the reference work "Multiprocessors and Parallel Processing" by Phillip H. Enslow published by John Wiley and Sons, New York, 1974), this invention relates an architecture approach for implementing information processing systems. (Appendix VV is a catalogue of references cited.) Since there are many architectural approaches in existence in the art for the implementation of such systems, it is desirable to classify these systems so that the proper position of my invention may be identified with respect to the prior art approaches. Since there is a great disparity in the use of nomenclature in the information processing architecture art, it is also necessary to identify the nomenclature which shall be used to specifically define my invention and shall also permit contrasting my invention with the prior art.
Three differing parameters may be employed to characterize the architecture of information processing systems:
1. The number of processors utilized in the system in addition to the number of peripheral equipments employed. For the purpose of describing my invention, I shall call peripheral equipments by the nomenclature "external processors" since I consider such devices (which include line printers, card readers, keyboards and display devices) external to that portion of a system implemented in accordance with my invention which is new in the art. PA0 2. The manner of interconnecting the processors of a system which is also called the topology of a system. In this regard, the taxonomical system for differentiating different interconnection schemes as defined in the paper "Computer Interconnection: Taxonomy, Characteristics and Examples" by G. A. Anderson and E. D. Jensen which appears in "Computing Surveys" Volume 7, No. 4, December 1975, published by the Association for Computing Machinery (ACM) is used in my description. PA0 3. The functionality assigned to the processors of a system. In this regard, the external processors of a system usually have well-defined functional roles (such as listing the results of computations on a line printer). In contrast, the internal processors (those portions of the system not considered peripheral devices in the common nomenclature) may be of either a general purpose or of a dedicated function type. Such systems are also often called "homogeneous" systems if they utilize general purpose processors or "heterogeneous" if each processor is designed and built to perform only a selected set of functions. The differentiation of such systems and the advantages of each are clearly outlined in the current art in the paper "Innovations in Heterogeneous and Homogeneous Distributed Function Architectures" E. C. Joseph, published in the Institute for Electrical and Electronic Engineers (IEEE) Computer Magazine, March 1974. PA0 1. Memory for containing the data to be manipulated as well as the programs which define the order of manipulations of the data. This will also be referred to as the data structure of the system and it should be noted that data structures may be implemented in hardware using general purpose memories (such as central random-access memory) or in a specialized functional manner (such as hardware stacks and queues as defined, for example, in the text by Robert R. Korfphage entitled "Discrete Computational Structures" published in 1974 by Academic Press, Inc., New York, and in the textbook "Computer Architecture" by Caxton Foster published in 1970 by Van Nostrand Reinhold Company, New York). PA0 2. Mechanisms for manipulating the data in the data structures (memories) of the system. In practice, these may be of the general purpose type such as an arithmetic-logic unit or of a special purpose nature such as a string processor for manipulating character-oriented data structures. PA0 3. Control mechanisms which effectively activate the data manipulations as a function of interpreting the commands also called instructions in the program. PA0 4. Input/output mechanisms which allow the transmission of information to and from the external processors (peripheral equipment) and in so doing allow the information processing system to perform a useful purpose (for otherwise if there were no external processors, the system could neither obtain the data to be processed nor communicate the results of its computations). PA0 1. Whether messages between processors are communicated directly between one processor to another or possibly indirectly in which case the message must first be communicated through a third processor and with possible modification then communicated to the second intended processor. In my invention, message communication which I call "instruction transfer" in general may travel through intervening processors with modification and thus in my approach message transfer is indirect. PA0 2. Whether the switching of messages from one processor to another is accomplished by a centralized mechanism (such as a so-called "cross-bar" network which is described in Anderson's paper) or on a decentralized basis wherein each processor may control the switching of messages between itself and other processors in the system with which messages can be communicated. In this respect, my invention utilizes decentralized switching using a technique and structure to which I refer as "control arcs" and defined more fully in the following portions of the specification. PA0 3. Whether the physical paths for message (instruction) communication are shared amongst more than two processors or dedicated for communication between a first and second processor. In my invention, message paths are dedicated and the physical hardware required to form each instruction communication path is called a "control arc." PA0 4. Whether the network of communication paths and placement of processors within this network is arranged on the basis of a regular pattern or alternately on the basis of an irregular pattern. In my invention, each practical implementation generally results in an irregular pattern. PA0 1. Memory requirements are reduced since only sufficient memory to contain the high level language is necessary (the additional memory required to save the machine language program in prior art devices is not needed). PA0 2. The overall implementation of programs is simpler since only one step is necessary to run a program. PA0 1. Use numbers as the basis for computations. PA0 2. Perform operations on these numbers such as add and subtract to produce other numbers. PA0 1. The elements (data) to be manipulated are strings. PA0 2. Operations over the strings include the mathematical operations "alternation" and "concatenation."
With regards to the functionality of processors in a given system, four main functional areas may be identified:
With regards to the number of processors employed in a system, my invention along with many other approaches refers to a concept in which more than one processor is used in addition to any number (but at least one) of external processors. The principal advantage in these approaches over single processors systems being a net increase in performance as measured by how long in time it takes to execute a given program and/or how short a time the system can respond to a stimulus from an external processor.
With regards to the functionality of processors in a system built in accordance with my invention, it is a feature of my approach to allow specific dedicated special purpose functions to be assigned and built into each processor. For example, if two different data structures are needed in a system, then in my approach two different processors are designed and each placed at an appropriate point in the interconnection network of the system. Since the functions of the system are "distributed" amongst the processors in a system, then my invention appropriately falls into the category of "distributed function architecture" machines. Further, since each processor in my approach generally has a different design and different capabilities from each of the other processors in the system, my approach falls into the category of "heterogeneous distributed function architecture systems" in the nomenclature of the Joseph reference.
With regards to the topology of interconnection of processors in a system, the Anderson and Jensen paper define a taxonomy on the basis of four parameters which briefly are:
In summary then, under the structural taxonomy convention defined by Anderson and Jensen, my invention reconstitutes a multiple processor information processing system utilizing indirect message (instruction) transmissions (communication) which are decentrally switched over dedicated message (instruction) paths resulting in a generally irregular arrangement of processors, and referred to as an IDDI category from the first letters of the words "indirect," "decentrally," "dedicated," and "irregular."
2. Description of the Prior Art
In contrast, the approach of Frank J. Perpiglia as defined in U.S. Pat. No. 3,905,023, Sept. 9, 1975, entitled "Large Scale Multi-Level Information Processing System Employing Improved Failsaft [Sic] Techniques," also refers to a system having more than one processor in addition to external processors. In the Perpiglia approach, each processor may communicate directly to any other second processor by way of a centralized non-dedicated switching network. In addition, the arrangement of processors when viewed from the block diagram level looks the same for any machine implemented in accordance with the Perpiglia concept independent of the number of processors employed and thus a machine under this concept has a regular interconnection topology. Thus, although my invention is similar to the Perpiglia approach in the sense of utilizing multiple processors, my structure varies from the Perpiglia architecture on the basis of all four major structural taxonomy parameters. In this regard, the disclosures of L. D. Amdahl et al in U.S. Pat. No. 3,226,689, Dec. 28, 1965, entitled "Modular Computer System Master Disconnect Capability"; Frederich V. Rehhauser et al in U.S. Pat. No. 3,665,421, May 23, 1972, entitled "Information Processing System Implementing Program Structures Common to Higher Level Program Languages"; and R. C. Richmond et al in U.S. Pat. No. 3,374,465, Mar. 15, 1968, entitled "Multiprocessor System Having Floating Executive Control" all describe computer architectures or means for controlling the interaction amongst the processors of systems having structural topology similar to the Perpiglia architecture and thus vary significantly in the manner of implementation and intended application from my invention.
Another prior art approach for implementing systems utilizing multiple processors is the "Electronically Controlled Microelectronic Cellular Logic Array" as disclosed by S. E. Wahlstrom in U.S. Pat. No. 3,473,160, issued Oct. 14, 1969. In this approach, direct message transmission is accomplished over dedicated decentrally switched paths. However, all processors according to Wahlstrom are required to be identical in design and each processor is required to have a fixed set of connections with an identical number of other processors so that the network is always regular and thus varies from my approach on the basis of regularity or irregularity of interconnection. The Wahlstrom approach also differs from my approach on the basis of functionality of usage of each processor. In the Wahlstrom arrangement, as well as in similar cellular array concepts such as the ILLIAC-4 computer (described in the previously cited Enslow reference ) and the theoretical Solomon approach (described in the Bell reference), each processor is capable of performing the functions of any other processor in the system and thus each processor is a general purpose processor which is, therefore, burdened with the overhead of hardware normally associated with general purpose processors. In architecture according to my invention, each processor is designed for each intended application to perform only a subset of the necessary system functions and thus my graph architecture system can be built at lower cost as less hardware is involved, or conversely, the processor may be of higher performance since specialized circuitry such as custom large-scale integrated circuits may be employed in a single specific processor without having to supply the same circuitry in all other processors in the system.
As further background to my invention, it is pointed out that a significant problem of multiple processor systems is a problem called "deadlock" and otherwise called "deadly embrace." This problem results from the possibility, as a function of how a given information processing system is programmed, that a situation may arise such that several processors request the services of other processors in the system in such a way that none of the processors can continue its activities causing the system to be deadlocked and precluding further work. The theoretical solution of this problem, as it applies to software management, is described in the article by E. G. Coffman, Jr., et al entitled "System Deadlocks" published in the ACM Computing Surveys Journal, Vol. 3, No. 2, June 1971.
Although solutions exist to this problem (as well as associated problems such as data contention) the programmer is burdened with ensuring that deadlock can never occur and this is very difficult in large systems in which many programmers are involved. A better solution is to have an architecture design of a multiple-processor system which automatically (and without programmer knowledge) inhibits the system's operation in such a way as to eliminate any possible deadlock (and since the solution is in hardware, the programmer can not do anything to make the system deadlock). The extensions necessary to the theoretical art of computer science required for such a hardware solution have been accomplished by me and reported in my doctoral thesis (Ph.D., University of Massachusetts, 1976) entitled "A Class of Multiple Processor Computers with Grammar Directed Control" published in 1976 by University Microfilms, Ann Arbor, Mich. This work in abbreviated form appears in my article "Grammar Based Multiple Processor Design," 1977 IEEE Micro-Computer Conference Record and also my chapter entitled "A Design Approach for Multiple Processor Computers" which appears as Chapter 2 in the book "Micro-computer Design and Applications" edited by Samuel C. Lee and published in 1977 by Academic Press, Inc., New York. In the thesis, I show from a theoretical point of view that a multiple processor system can be designed with no inherent deadlock problems by allowing a high-level definition of the information processing system to be specified using a notation which I call "control grammars." Well defined operations on such a control grammer (which is based upon the theory of formal languages as described in the paper "Syntax Directed Transduction" by P. M. Lewis, 2nd, and R. E. Stearns appearing in the ACM Journal, Volume 15, No. 3, July 1968, and further expanded in the textbook entitled "Compiler Design Theory" by P. M. Lewis, J. Rosenkrantz and R. E. Stearns published by Addison-Wesley Co., Reading, Mass., 1976) are used to generate the definition of interconnection of processors in the system. The relationship between the architecture of a system and its definition by control grammars is based upon a mathematics common to both the system and the grammar which is known as "graph-theory" and is discussed in the previously mentioned text by Korfphage. The main theoretical concept here is that both the interconnection of processors in an information processing system and the relationship of elements in a grammar may be depicted as "graphs" in the previously mentioned mathematical theory. It is a purpose of my invention to disclose the concept of and the means of implementing such systems without burdening the user to understanding the aforementioned mathematical theory. Since the theoretical basis of my invention is the mathematics of graphs, I have chosen to call my invention the "Graph Architecture Information Processing System."
Reference to prior art work must include the disclosure of Saul B. Dinman of "Direct Function Processor" in U.S. Pat. No. 3,631,401 issued Dec. 28, 1971. In this approach, the structural taxonomy of the system is similar to that in my system except that the interconnection of processors in limited to two levels of control wherein one level is a master processor for controlling a plurality of subprocessors. In the Dinman architecture approach, no deadlock can occur because the subprocessors are not allowed to communicate with each other, thus avoiding the deadlock issue altogether.
Another system which avoids the deadlock issue is the "Data Processing System Having Pyramidal Hierarchy Control Flow" defined in U.S. Pat. No. 3,962,685 issued June 8, 1976, to Albert P. Belle Isle and assigned to the same assignee as is my invention. In the Belle Isle architecture, any number of levels of control may be employed potentially achieving a much more powerful system than the Dinman architecture, but one single processor is still required to be the master driver of the system in such a way that full utility of the processors is limited. In my approach, there is no requirement for a first high-level master processor since deadlock is resolved on the basis of the architecture topology in conjunction with the aforementioned theory. Thus, my invention allows nearly the full performance capabilities of systems such as that defined by Perpiglia but without the burdening of software to resolve deadlock and associated problems. As in-depth discussion of the relationship of these inventions is given in the following detailed portions of my specification.
My invention also includes and implements a new concept for directly executing high level languages. High level languages differ from what is commonly referred to as machine language. In machine language, the programmer is given a set of instructions, each having a different numerically-coded operation code (which will be abbreviated as "opcode") and data parameters (which will be called simply "data"). A program is constructed by defining a specific order of these instructions. In a program, the same instruction may appear many times. When executed by a computer, the instructions are read out and the operation defined by the opcode is executed in the order of the instructions in the program. The main feature of machine language instructions is that an instruction having a specific opcode is always executed in the same way independently of instructions previously executed.
In contrast, in a high level language program, a relatively free form of data is used and programs consist of ordered sequences of alpha-numeric characters instead of the numeric data which forms the basis of machine language. It is a specific objective of a high level language to represent a form which is readily indentified by the user and relates to the type of problems being solved.
For example, in the high level language BASIC described in the previously-cited Lewis (1976) reference, the programmer is allowed to write algebraic equations as opposed to listing a sequence of memory reads, accumulator additions and the like which typify machine language programming. A peculiarity of high level languages is that a single character sequence can have entirely different meanings under different circumstances. For example, the characters "SIN" could mean a variable name or mean the sine trigonometric function. This is in sharp contrast to machine language in which a specific operation code number (opcode) always has a specific meaning.
In prior art systems, high level language capabilities are implemented by use of a program, written in machine language, which is capable of converting a high level language character sequence to the ordered instruction sequence of a machine language which is subsequently executed. This process of converting a high level language program to a machine level language program is usually called "compilation" and the mathematical process of deciphering the intended meaning of the high level language program is called "parsing." A discussion of these terms may be found in the textbook, "The theory of Parsing, Translation and Compiling" by A. V. Aho and J. D. Ullman published by Prentice-Hall, Inc., Englewood Cliffs, N.J., 1972.
In my invention, a specific processor called a METAPROCESSOR is used to interpret a high level language and generate the appropriate machine level instructions to be executed by other processors. The advantages of this approach over prior art systems include:
In my invention, the METAPROCESSOR may be reprogrammed to allow changes in the high level language or allow execution of programs in different high level languages. To maintain maximum speed, the programming of the METAPROCESSOR is accomplished in a machine level language. Since the language of the METAPROCESSOR allows the definition of a high level language, the METAPROCESSOR instruction set effectively defines a "meta-language". . . that is a language for defining a language (in reference see the previously-cited Aho and Ullman text). Since the METAPROCESSOR of my invention allows the direct programming of operations required for parsing and metalanguage operations, I have chosen to call this particular portion of my invention by the name METAPROCESSOR.
Prior art systems for directly executing high level languages are typified, for example, by the "Information Processing System Implementing Program Structures Common to High Level Program Languages" as defined in the above-cited U.S. Pat. No. 3,665,421 to Rehhauser et al. In the Rehhauser arrangement, hardware is added to a multi-processor system of the Perpiglia architecture to allow direct execution of high level languages.
In contrast, the concept in my METAPROCESSOR is to supply a dedicated function processor for use in systems which support the use of such processors as, for example, my own graph architecture. In addition, within the architecture of a given system, more than one METAPROCESSOR may be employed to speed up the execution of programs by assigning specific METAPROCESSORS to interpret (parse) different portions of a high level language. It is also a feature of my invention to use "classifier" and "push-down" stack mechanisms to allow the direct implementation of the language types called LL(1) as defined in the previously-mentioned Lewis text, these circuits being new and novel in the art of directly executed high level languages.
My invention also includes and implements a novel concept for performing string computations. By a "string" is meant a data structure formed by an ordered sequence of data characters. By a "character" is meant a data word of fixed size (usually 8 binary digits). This is in contrast to prior art computing systems which:
In string computing:
String computations are useful in systems in which the problems to be solved are inherently non-numeric in nature, for example, the analysis of inputs from a student in a computer-aided instruction system to determine if the student has correctly answered a question.
In prior art systems, string computations are performed by using softward algorithms on arrays of numbers which represent strings. Typical languages which support such computation are the LISP language (as defined in reference "LISP 1.5 Primer" by Clark Weissman and published by Dickenson Publishing Co., Inc., Belmont, California, 1967) and the SNOBOL language (as described in the text "A SNOBOL 4 Primer" by R. E. Griswold and M. T. Griswold published by Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973).
As opposed to prior art systems, in my invention hardware "stacks" are used to allow a significant speed-up of string computation operations for a modest system cost. The stack approach also allows a significant reduction in program size for specific problems when compared to solutions of these problems in prior art systems. My invention takes advantage of current art high speed semiconductor memory technology to implement the hardware stacks. No predecessor hardware string processor devices appear in the prior art.
My invention also relates to an approach for storing graphic information in a reduced form and for generating complex visual presentations on a variety of different types of display devices using the same hardware processor. For example, the same processor is used to generate images for a raster scan cathode ray tube (CRT) display device and also drives a flat panel dot-addressable plasma panel type display. Prior art systems are typified by the "Method and Apparatus for Point Plotting of Graphical Data From a Coded Source Into a Buffer and For Rearranging That Data for Supply to a Raster Responsive Device" as defined in U.S. Pat. No. 3,973,245, Aug. 3, 1976, to Karl A. Belser. In contrast, in my invention, the same hardware is utilized to drive dissimilar display devices.
It is an object of the present invention to provide an information processing system having the ability to directly execute high level user languages.
It is a further object to provide a system of modular design where a plurality of processing elements may be utilized each performing different functions within the system.
It is a further object to provide a system in which similar processing elements are utilized to direct the activities of dissimilar external processors.
It is a further object to provide a system of processing elements having the capability of constructing and displaying images of arbitrary complexity from a specified set of primitive images.
It is a further object to provide a system of processing elements having the ability to develop a tree-structured organization of display image definitions.
It is a further object to provide a system including processing elements having the capability of converting information produced by a first external processor to information in a form characteristically produced by a dissimilar second external processor. The interpretation of information produced by the first processor is re-definable.
It is a further object to provide a system including processing elements having the capability of interpreting high level user languages and directing activities of the system in accordance with such interpretations.
It is a further object to provide a system including processing elements having the capability of interpreting high level user languages and directing activities of the system in accordance with such interpretations.
It is a further object to provide a system including processing elements having the ability to manipulate strings of data to effect reduction of language based data (non-numeric computations), parsing of high level algorithm programming language and editing of data files.
These and further objects of the invention will become apparent by referring to the following detailed description and accompanying drawings.